// master公式计算递归的时间复杂度
// T(N) = a*T(N/b)+O(N^d)
// log(b,a) > b 时间复杂度为O(N^log(b,a))
// log(b,a) = b 时间复杂度为O(N^d*logN)
// log(b,a) < b 时间复杂度为O(N^d)
// 下面例子中的时间复杂度是T(N) = 2*T(N/2)+O(1)，其中a=2是应为调用递归两次b=2是应为取中点数据量减少一半
// 场景求一个数组中arr[L..R]范围上的最大值
import Logarithm from './7.对数器'
import insertionSort from './5.插入排序'
const getMaxArr = (arr: Array<number>): number =>{
    return process(arr,0,arr.length-1)
}
const process = (arr:number[],L:number,R:number) : number => {
    if(L == R) return arr[L]
    const mid = L + ((R-L)>>1)
    const leftMax = process(arr,L,mid)
    const rightMax = process(arr,mid+1,R)
    return Math.max(leftMax,rightMax)
}
const measurementTime = (fn:Function): number => {
    const time = Date.now()
    for(let i = 0; i < 10000000 ; i++) {
        const arr = Logarithm.generateRandomArrays(100,100)
        if(arr.length == 0)  continue
        const data = fn(arr)
        data instanceof Array ? data[0] : null
    }
    return Date.now()-time
}
console.log(measurementTime(getMaxArr),measurementTime(insertionSort))
// console.log(getMaxArr([1,2,3,4,11111,6]))
export default process